package com.LeeCode;

/**
 * 节点与其祖先之间的最大差值
 */

public class Code1026 {
    public static void main(String[] args) {
        Integer[] arr = {8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1026().maxAncestorDiff(root));
    }

    int ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return ans;
    }

    private void dfs(TreeNode root, int mx, int mn) {
        if (root == null) return;
        mx = Math.max(mx, root.val);
        mn = Math.min(mn, root.val);
        ans = Math.max(ans, mx - mn);
        dfs(root.left, mx, mn);
        dfs(root.right, mx, mn);
    }
}
